package 高效制胜._11;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/22 9:48
 * 矩阵中的最长递增路径
 * 算法：记忆化搜索
 * 回溯会超时
 * 使用记忆化搜索将已经遍历元素的最长递增路径存起来，
 * 当其他点遍历到这个点时，直接返回该点对应的数即可
 */
public class _329 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2}, {2, 3}};
//        int[][] matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
        System.out.println(new _329().longestIncreasingPath(matrix));
    }

    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int row, col;

    public int longestIncreasingPath(int[][] matrix) {
        row = matrix.length;
        col = matrix[0].length;
        int ans = 0;
//        boolean[][] visited = new boolean[row][col];
        int[][] memo = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
//                int dfs = dfs_huisu(matrix, visited, i, j, 1);
                int dfs = dfs(matrix, memo, i, j);
                ans = Math.max(ans, dfs);
            }
        }
        return ans;
    }
    int dfs(int[][] matrix, int[][] memo, int i, int j) {
        if (memo[i][j] != 0) return memo[i][j];
        ++memo[i][j];
        for (int[] dir : directions) {
            int newI = i + dir[0], newJ = j + dir[1];
            if (newI >= 0 && newI < row && newJ >= 0 && newJ < col
                    && matrix[i][j] < matrix[newI][newJ])
                // 这里的 +1 是加上自己
                memo[i][j] = Math.max(memo[i][j], dfs(matrix, memo, newI, newJ) + 1);
        }
        return memo[i][j];
    }

//    int dfs_huisu(int[][] matrix, boolean[][] visited, int i, int j, int ans) {
//        int res = ans;
//        visited[i][j] = true;
//        for (int[] dir : directions) {
//            int newI = i + dir[0], newJ = j + dir[1];
//            if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length
//                    && matrix[newI][newJ] > matrix[i][j]) {
//                if (!visited[newI][newJ]) {
//                    int dfs = dfs_huisu(matrix, visited, newI, newJ, ans + 1);
//                    res = Math.max(res, dfs);
//                }
//            }
//        }
//        visited[i][j] = false;
//        return res;
//    }

}
